perm filename A03[154,RWF] blob
sn#790313 filedate 1985-03-25 generic text, type C, neo UTF8
COMMENT ā VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 Theorem: No algorithm can exist, which for every program x and datum d,
C00012 ENDMK
Cā;
Theorem: No algorithm can exist, which for every program x and datum d,
determines whether or not x halts when presented with d.
This theorem is a relative of the barber paradox. The barber in a certain
town has a sign on his wall saying "I shave those men, and only those,
who do not shave themselves." Is the sign true or false? Surprisingly,
it must be false, because all answers to the question whether the barber
shaves himself are self-contradictory.
(1) The barber shaves himself. Then he is not one of those who do not
shave themselves, and according to the sign he would not shave himself.
(2) The barber does not shave himself. Then, according to the sign, he
would shave himself.
First we show that the theorem is true for programming systems (like machine
language) where the program can act on itself, perhaps by making a copy of
itself and working on that. Suppose we have a procedure h(x,d) which yields
True if program x halts on datum d, and False if x runs forever on datum d;
notice that h itself halts on all inputs.
Design a program which does this:
(1) It reads its input datum to a variable d.
(2) It makes a copy of itself, which we will call p.
(3) It executes h(p,d) to determine whether it is supposed to halt or not.
(4) If the result h(p,d) is True, it enters an infinite loop. Otherwise
it prints 0 and halts.
Like a barber, who can't be given an algorithm to apply to himself that
determines whether he shaves himself or not (if there were such an algorithm,
the barber could use it and then do the opposite of what it says he does),
a program, given an algorithm to test itself for stopping, can be designed
to do the opposite.
If the program is written in a system which, like Pascal, does not provide
for self-reference, we can get around that by letting it _read_ a copy of
itself, decide whether it is supposed to stop or loop, and do the opposite.
The program will do the following:
(1) It reads an input string into variable p.
(2) It executes h(p,p) to determine whether p halts when given a copy of
itself as data or not.
(3) If h(p,p) is True, it enters an infinite loop; if False, it prints 0
and stops.
If we had the procedure h, we could construct such a program. Say the
program is the string x. Then present it with x as input. Two cases arise.
(1) h(x,x) is True. Then Step 2 gets h(p,p) = True, the program enters a loop,
and h(x,x) should be False.
(2) h(x,x) is False, Step 2 gets h(p,p) = False, the program terminates, and
h(x,x) should be True.
Suppose we weaken the assumptions of the theorem. Let h(x,d) be a total
function, which if true guarantees that program x halts on datum d, but if
False does not necessarily mean x runs forever on datum d. We build a program
a to:
(1) Read datum d
(2) Execute h(d,d)
(3) If h(d,d) is True, print U(d,d)+1. Otherwise, print 0.
By our assumptions, program a halts on all inputs. If we execute kprogram a,
presenting it with a copy of itself as its input datum, and h(a,a) is True,
a will print a result which is both U(a,a) and U(a,a)+1, a contradiction.
Therefore h(a,a) must be false.
So a is a program which, we can readily see, always halts, but h(a,a) can't
discover that. No matter how clever an algorithm we devise to identify some
executions which halt, it is technically easy to find an execution which
will halt but which our "clever" algorithm can't identify as halting.
Why can't algorithm h do what we just did, and deduce that program a halts
on all data? That deduction depends on the knowledge that h(x,d) always
halts, and that h(x,d) = True implies that U(x,d) halts. In particular
cases, this knowledge may be unattainable.
In general, we may get into all the complications of self-reference and
self-modification even in a programming language that makes no explicit
provision for it. Let a program p read an input x, assumed to be a program,
and make a second "working" copy, y:=x. It can then apply arbitrary
transformations (y:=f(y) say) to y, and execute x with y as datum by
evaluating U(x,y). If we then execute p, giving it a copy of itself as its
datum, the program it is modifying and executing is itself.
How about a program that belongs to a family of similar, but related,
programs? Can they be, not only self-referential, but "each-other-referential"?
Easy. Let each of programs p1 and p2 read data x1, and x2; the rest of p1 and p2
is written on the assumption that, when the programs are executed, x1 will
contain a copy of p2. Having written the programs, we can provide copies on
the input files, justifying the assumption.
Now, how about a whole infinite family of programs p1, p2, p3,...? Obviously
p1 (say) can't refer to all of them unless there is some relation among
them, since only finitely many could be read in. Let's say that each is a
special case of a program with one more parameter:
pi(x)=q(i,x)
We assume (the s-m-n theorem of recursive function theory) that, given a
program for q, a program for pi can be constructed. Now we write a program
which reads a datum into variable q, assumed to be the general 2-parameter
program; it also reads a datum into variable i, assumed to identify the pi
that is wanted. A specializing algorithm spec(j,q) is presumably available
to get pj from q for any j. By executing spec(i,q) the specialized program
gets a copy itself. It can get a copy of one of the others, pj, by
executing spec(j,q). When the (general) program is written, a copy of it
is provided as the datum to be read into q, and the specializing value
is provided to be read into i.
Example: to construct infinitely many different programs all of which,
on input x, print x+1.
General program:
READ q; (copy of the general program)
READ i; (specialized value, identifying pi)
FOR j:=1 TO i-1 DO
IF spec(j,q)=spec(i,q)
THEN WHILE TRUE DO WRITE('HELP!');
READ X; WRITE (x+1).
Notice that p1 never executes the FOR-loop, so it reads x and prints x+1.
Then p2 checks itself against p1, and, if it finds p1=p2, p2 loops, which
is not possible since p1 doesn't loop.